#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    bool check(TreeNode* t1,TreeNode* t2)
    {
        if(!t2) return true; // 已经遍历完t2
        if(!t1) return false; // t1比t2 提前遍历完
        if(t1 && t2 && t1->val == t2->val) 
            return check(t1->left,t2->left) && check(t1->right,t2->right);
        return false;
    }
public:
    bool checkSubTree(TreeNode* t1, TreeNode* t2) {
        if(!t1 || ! t2) return false;
        return check(t1,t2) || checkSubTree(t1->left,t2) || checkSubTree(t1->right,t2);
    }
};
